package class7;

import common.Node;

/**
 * 题目1：
 * 两个环形链表，返回第一个相交节点，如果不相交返回null
 */
public class Code03_LoopNode2 {
    public static void main(String[] args) {

    }

    public static Node getIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node loop1 = isloop(head1);
        Node loop2 = isloop(head2);
        if (loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }
        if (loop1 != null && loop2 != null) {
            return bothLoop(head1, loop1, head2, loop2);
        }
        return null;
    }

    // 返回两个链表相交的首节点
    public static Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;
        while (cur1 != null) {
            cur1 = cur1.next;
            n++;
        }
        while (cur2 != null) {
            cur2 = cur2.next;
            n--;
        }
        // 当两个链表的尾节点不同时，则不相交
        if (cur1 != cur2) {
            return null;
        }
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        n = Math.abs(n);
        // 让长链表先走n步，然后再一起走
        while (n != 0) {
            cur1 = cur1.next;
            n--;
        }
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    // 判断链表是否有环，并返回入环的第一个节点
    public static Node isloop(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node s = head.next;
        Node f = head.next.next;
        while (f != s) {
            if (f.next == null || f.next.next == null) {
                return null;
            }
            f = f.next.next;
            s = s.next;
        }
        f = head;
        while (f != s) {
            f = f.next;
            s = s.next;
        }
        return s;
    }

    /**
     * 1. loop1 和 loop2分别为进入环的首节点
     */
    public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
        Node cur1 = null;
        Node cur2 = null;
        // 当head1 和 head2 进入loop的节点相同时
        if (loop1 == loop2) {
            cur1 = head1;
            cur2 = head2;
            int n = 0;
            while (cur1 != loop1) {
                cur1 = cur1.next;
                n++;
            }
            while (cur2 != loop2) {
                cur2 = cur2.next;
                n--;
            }
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n != 0) {
                cur1 = cur1.next;
                n--;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        } else {
            cur1 = loop1.next; // cur1 往下走
            while (cur1 != loop1) {
                if (cur1 == loop2) {
                    return loop1; // 这里返回loop1或loo2都行
                }
                cur1 = cur1.next;
            }
            // 当loop转一圈后，依然没有遇到loop2，则不相交
            return null;
        }
    }

}
